package codeRandomThoughts.Test257二叉树的所有路径;

import codeRandomThoughts.utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

//二刷
public class Solution2 {
    List<Integer> result;
    List<String> results;

    public List<String> binaryTreePaths(TreeNode root) {
        result = new ArrayList<>();
        results = new ArrayList<>();
        backtracking(root);
        return results;
    }

    //应该是第一道涉及到回溯的题目
    public void backtracking(TreeNode root) {
        result.add(root.val);
        //终止条件
        if (root.left == null && root.right == null) {
            addToResults(results, result);
            return;
        }

        //单层递归逻辑
        //根左右

        //左
        if (root.left != null) {
            backtracking(root.left);
            result.remove(result.size() - 1);
        }

        //右
        if (root.right != null) {
            backtracking(root.right);
            result.remove(result.size() - 1);
        }
    }

    public void addToResults(List<String> results, List<Integer> result) {
        if (result.size() == 0) {
            return;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < result.size() - 1; i++) {
            sb.append(result.get(i));
            sb.append("->");
        }
        sb.append(result.get(result.size() - 1));
        results.add(new String(sb));
    }
}
